package _05_二叉树;

import java.util.Arrays;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/maximum-binary-tree/
 *
 * @Author: haogege
 * @Date: 2021/8/27
 */
public class _654_最大二叉树 {

    public static void main(String[] args) {
        _654_最大二叉树 v = new _654_最大二叉树();
        int[] ins = {3, 2, 1, 6, 0, 5};
        int[] parentIndex = v.findParentIndex(ins);
        System.out.println(Arrays.toString(parentIndex));
    }

    // 查找二叉树的父节点在数组中的索引
    public int[] findParentIndex(int[] nums) {
        if (nums == null || nums.length < 2) return new int[0];
        // 结果
        int[] result = new int[nums.length];
        // 第一个左边元素的索引
        int[] maxLeft = new int[nums.length];
        // 第一个右边元素的索引
        int[] maxRight = new int[nums.length];
        // 填充默认值
        Arrays.fill(result, -1);
        Arrays.fill(maxRight, -1);
        Arrays.fill(maxLeft, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                // 弹出顶部元素
                Integer index = stack.pop();
                // 弹出元素右边第一个比他大的元素就是nums[i]
                maxRight[index] = i;
            }
            if (!stack.isEmpty()) {
                // 查看栈顶元素，其为左边第一个比他大的元素
                Integer index = stack.peek();
                maxLeft[i] = index;
            }
            stack.push(i);
        }
        for (int i = 0; i < maxLeft.length; i++) {
            if (maxLeft[i] == -1 && maxRight[i] == -1) continue;
            if (maxLeft[i] == -1) {
                result[i] = maxRight[i];
            } else if (maxRight[i] == -1) {
                result[i] = maxLeft[i];
            } else if (nums[maxLeft[i]] < nums[maxRight[i]]) {
                result[i] = maxLeft[i];
            } else {
                result[i] = maxRight[i];
            }
        }
        return result;
    }

    // 构造最大二叉树
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // 找出数组元素中最大
        return constructMaximumBinaryTree(nums, 0, nums.length);
    }

    public TreeNode constructMaximumBinaryTree(int[] nums, int begin, int end) {
        // 递归出口
        if (begin == end) return null;

        int maxIndex = begin;
        // 找出数组元素中最大
        for (int i = begin + 1; i < end; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(nums[maxIndex]);

        // 构造左边
        root.left = constructMaximumBinaryTree(nums, begin, maxIndex);

        // 构造右边
        root.right = constructMaximumBinaryTree(nums, maxIndex + 1, end);

        return root;
    }
}
